package com.ssyan.sort;

/*
    快速排序：基于分治思想
            确定分界值(数组首位元素)，将数组相对于分界值左右排序，确定分界值的索引值
            数组由分界值处分为左右两块，分别重新确定分界值（新数组首位元素）再排序再分割，依次类推
            分割并排序完所有的最小子数组，再反向合并，将分界值依次插入
    时间复杂度：O(nlogn),最坏情况时：O(n^2)
    排序稳定性：不稳定
 */
public class Quick {
    /*
        比较v元素是否小于w元素
     */
    private static boolean less(Comparable v,Comparable w) {
        return v.compareTo(w)<0;
    }

    /*
        数组元素i和j交换位置
     */
    private static void exch(Comparable[] a,int i,int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    //对数组内的元素进行排序
    public static void sort(Comparable[] a) {
        int lo=0;
        int hi=a.length-1;
        sort(a,lo,hi);

    }

    //对数组a中从索引lo到索引hi之间的元素进行排序
    private static void sort(Comparable[] a,int lo,int hi) {
        //安全性校验
        if (hi<=lo) {
            return;
        }

        //需要对数组中的lo索引到hi处的元素进行分组（左子组和右子组）
        int partitionindex = partition(a, lo, hi);//返回分界值位置变化后的索引

        //让左子组有序
        sort(a,lo,partitionindex-1);

        //让右子组有序
        sort(a,partitionindex+1,hi);
    }

    //对数组a中，从索引lo到索引hi之间的元素进行分组，并返回分组界限对应的索引
    /*
    实现思想：
        双指针确定分界值索引：
            left指针：lo
            right指针：hi+1
        1.两指针分别指向数组的头部和尾部
        2.先从尾部向头部搜索比分界值小的元素，搜索到即停止，记录指针位置
        3.再从头部向尾部搜索比分界值大的元素，搜索到即停止，记录指针位置
        4.交换当前左右指针的元素
        5.重复2,3,4，直到left>right
    */
    public static int partition(Comparable[] a,int lo,int hi) {
        //确定分界值
        Comparable key = a[lo];

        //定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置
        int left = lo;
        int right = hi+1;

        //切分
        while (true) {

            //先从右往左扫描，移动right指针，找到一个比分界值小的元素，停止
            while (less(key,a[--right])) {
                if (right==lo){
                    break;
                }
            }
            //再从左往右扫描，移动left指针，找到一个比分界值大的元素，停止
            while (less(a[++left],key)) {
                if (left==hi){
                    break;
                }
            }
            //判断 left>=right，如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可
            if (left>=right) {
                break;
            } else {
                exch(a,left,right);
            }
        }

        //交换分界值
        exch(a,lo,right);

        return right;
    }
}
